package 力扣日常刷题.木23一月.第07天307;

import java.util.ArrayList;
import java.util.List;

/**
 * @author 帅小伙
 * @date 2022/3/7
 * @description
 */
public class Demo06替换数组中的非互质数 {

    public List<Integer> replaceNonCoprimes(int[] nums) {
        var s = new ArrayList<Integer>();
        s.add(nums[0]);

        for (int i = 1; i < nums.length; i++) {
            s.add(nums[i]);
            while (s.size() > 1) {
                var x = s.get(s.size() - 1);
                var y = s.get(s.size() - 2);
                var g = gcd(x, y);
                if(g == 1) break;
                s.remove(s.size() - 1);
                s.set(s.size() - 1,x/g*y);
            }
        }
        return s;
    }

    public int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }


}
